home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Berkeley DB 1.8.5a / hash / hash_page.c < prev    next >
Text File  |  1995-06-20  |  23KB  |  947 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_page.c    8.7 (Berkeley) 8/16/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * PACKAGE:  hashing
  43.  *
  44.  * DESCRIPTION:
  45.  *    Page manipulation for hashing package.
  46.  *
  47.  * ROUTINES:
  48.  *
  49.  * External
  50.  *    __get_page
  51.  *    __add_ovflpage
  52.  * Internal
  53.  *    overflow_page
  54.  *    open_temp
  55.  */
  56.  
  57. #include <sys/types.h>
  58.  
  59. #include <errno.h>
  60. #include <fcntl.h>
  61. #include <signal.h>
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65. #include <unistd.h>
  66. #ifdef DEBUG
  67. #include <assert.h>
  68. #endif
  69.  
  70. #include <db.h>
  71. #include "hash.h"
  72. #include "page.h"
  73. #include "hash_extern.h"
  74.  
  75. static u_int32_t    *fetch_bitmap __P((HTAB *, int));
  76. static u_int32_t     first_free __P((u_int32_t));
  77. static int     open_temp __P((HTAB *));
  78. static u_int16_t     overflow_page __P((HTAB *));
  79. static void     putpair __P((char *, const DBT *, const DBT *));
  80. static void     squeeze_key __P((u_int16_t *, const DBT *, const DBT *));
  81. static int     ugly_split
  82.             __P((HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int));
  83.  
  84. #define    PAGE_INIT(P) { \
  85.     ((u_int16_t *)(P))[0] = 0; \
  86.     ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \
  87.     ((u_int16_t *)(P))[2] = hashp->BSIZE; \
  88. }
  89.  
  90. /*
  91.  * This is called AFTER we have verified that there is room on the page for
  92.  * the pair (PAIRFITS has returned true) so we go right ahead and start moving
  93.  * stuff on.
  94.  */
  95. static void
  96. putpair(p, key, val)
  97.     char *p;
  98.     const DBT *key, *val;
  99. {
  100.     register u_int16_t *bp, n, off;
  101.  
  102.     bp = (u_int16_t *)p;
  103.  
  104.     /* Enter the key first. */
  105.     n = bp[0];
  106.  
  107.     off = OFFSET(bp) - key->size;
  108.     memmove(p + off, key->data, key->size);
  109.     bp[++n] = off;
  110.  
  111.     /* Now the data. */
  112.     off -= val->size;
  113.     memmove(p + off, val->data, val->size);
  114.     bp[++n] = off;
  115.  
  116.     /* Adjust page info. */
  117.     bp[0] = n;
  118.     bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t));
  119.     bp[n + 2] = off;
  120. }
  121.  
  122. /*
  123.  * Returns:
  124.  *     0 OK
  125.  *    -1 error
  126.  */
  127. extern int
  128. __delpair(hashp, bufp, ndx)
  129.     HTAB *hashp;
  130.     BUFHEAD *bufp;
  131.     register int ndx;
  132. {
  133.     register u_int16_t *bp, newoff;
  134.     register int n;
  135.     u_int16_t pairlen;
  136.  
  137.     bp = (u_int16_t *)bufp->page;
  138.     n = bp[0];
  139.  
  140.     if (bp[ndx + 1] < REAL_KEY)
  141.         return (__big_delete(hashp, bufp));
  142.     if (ndx != 1)
  143.         newoff = bp[ndx - 1];
  144.     else
  145.         newoff = hashp->BSIZE;
  146.     pairlen = newoff - bp[ndx + 1];
  147.  
  148.     if (ndx != (n - 1)) {
  149.         /* Hard Case -- need to shuffle keys */
  150.         register int i;
  151.         register char *src = bufp->page + (int)OFFSET(bp);
  152.         register char *dst = src + (int)pairlen;
  153.         memmove(dst, src, bp[ndx + 1] - OFFSET(bp));
  154.  
  155.         /* Now adjust the pointers */
  156.         for (i = ndx + 2; i <= n; i += 2) {
  157.             if (bp[i + 1] == OVFLPAGE) {
  158.                 bp[i - 2] = bp[i];
  159.                 bp[i - 1] = bp[i + 1];
  160.             } else {
  161.                 bp[i - 2] = bp[i] + pairlen;
  162.                 bp[i - 1] = bp[i + 1] + pairlen;
  163.             }
  164.         }
  165.     }
  166.     /* Finally adjust the page data */
  167.     bp[n] = OFFSET(bp) + pairlen;
  168.     bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t);
  169.     bp[0] = n - 2;
  170.     hashp->NKEYS--;
  171.  
  172.     bufp->flags |= BUF_MOD;
  173.     return (0);
  174. }
  175. /*
  176.  * Returns:
  177.  *     0 ==> OK
  178.  *    -1 ==> Error
  179.  */
  180. extern int
  181. __split_page(hashp, obucket, nbucket)
  182.     HTAB *hashp;
  183.     u_int32_t obucket, nbucket;
  184. {
  185.     register BUFHEAD *new_bufp, *old_bufp;
  186.     register u_int16_t *ino;
  187.     register char *np;
  188.     DBT key, val;
  189.     int n, ndx, retval;
  190.     u_int16_t copyto, diff, off, moved;
  191.     char *op;
  192.  
  193.     copyto = (u_int16_t)hashp->BSIZE;
  194.     off = (u_int16_t)hashp->BSIZE;
  195.     old_bufp = __get_buf(hashp, obucket, NULL, 0);
  196.     if (old_bufp == NULL)
  197.         return (-1);
  198.     new_bufp = __get_buf(hashp, nbucket, NULL, 0);
  199.     if (new_bufp == NULL)
  200.         return (-1);
  201.  
  202.     old_bufp->flags |= (BUF_MOD | BUF_PIN);
  203.     new_bufp->flags |= (BUF_MOD | BUF_PIN);
  204.  
  205.     ino = (u_int16_t *)(op = old_bufp->page);
  206.     np = new_bufp->page;
  207.  
  208.     moved = 0;
  209.  
  210.     for (n = 1, ndx = 1; n < ino[0]; n += 2) {
  211.         if (ino[n + 1] < REAL_KEY) {
  212.             retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
  213.                 (int)copyto, (int)moved);
  214.             old_bufp->flags &= ~BUF_PIN;
  215.             new_bufp->flags &= ~BUF_PIN;
  216.             return (retval);
  217.  
  218.         }
  219.         key.data = (u_char *)op + ino[n];
  220.         key.size = off - ino[n];
  221.  
  222.         if (__call_hash(hashp, key.data, key.size) == obucket) {
  223.             /* Don't switch page */
  224.             diff = copyto - off;
  225.             if (diff) {
  226.                 copyto = ino[n + 1] + diff;
  227.                 memmove(op + copyto, op + ino[n + 1],
  228.                     off - ino[n + 1]);
  229.                 ino[ndx] = copyto + ino[n] - ino[n + 1];
  230.                 ino[ndx + 1] = copyto;
  231.             } else
  232.                 copyto = ino[n + 1];
  233.             ndx += 2;
  234.         } else {
  235.             /* Switch page */
  236.             val.data = (u_char *)op + ino[n + 1];
  237.             val.size = ino[n] - ino[n + 1];
  238.             putpair(np, &key, &val);
  239.             moved += 2;
  240.         }
  241.  
  242.         off = ino[n + 1];
  243.     }
  244.  
  245.     /* Now clean up the page */
  246.     ino[0] -= moved;
  247.     FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3);
  248.     OFFSET(ino) = copyto;
  249.  
  250. #ifdef DEBUG3
  251.     (void)fprintf(stderr, "split %d/%d\n",
  252.         ((u_int16_t *)np)[0] / 2,
  253.         ((u_int16_t *)op)[0] / 2);
  254. #endif
  255.     /* unpin both pages */
  256.     old_bufp->flags &= ~BUF_PIN;
  257.     new_bufp->flags &= ~BUF_PIN;
  258.     return (0);
  259. }
  260.  
  261. /*
  262.  * Called when we encounter an overflow or big key/data page during split
  263.  * handling.  This is special cased since we have to begin checking whether
  264.  * the key/data pairs fit on their respective pages and because we may need
  265.  * overflow pages for both the old and new pages.
  266.  *
  267.  * The first page might be a page with regular key/data pairs in which case
  268.  * we have a regular overflow condition and just need to go on to the next
  269.  * page or it might be a big key/data pair in which case we need to fix the
  270.  * big key/data pair.
  271.  *
  272.  * Returns:
  273.  *     0 ==> success
  274.  *    -1 ==> failure
  275.  */
  276. static int
  277. ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)
  278.     HTAB *hashp;
  279.     u_int32_t obucket;    /* Same as __split_page. */
  280.     BUFHEAD *old_bufp, *new_bufp;
  281.     int copyto;    /* First byte on page which contains key/data values. */
  282.     int moved;    /* Number of pairs moved to new page. */
  283. {
  284.     register BUFHEAD *bufp;    /* Buffer header for ino */
  285.     register u_int16_t *ino;    /* Page keys come off of */
  286.     register u_int16_t *np;    /* New page */
  287.     register u_int16_t *op;    /* Page keys go on to if they aren't moving */
  288.  
  289.     BUFHEAD *last_bfp;    /* Last buf header OVFL needing to be freed */
  290.     DBT key, val;
  291.     SPLIT_RETURN ret;
  292.     u_int16_t n, off, ov_addr, scopyto;
  293.     char *cino;        /* Character value of ino */
  294.  
  295.     bufp = old_bufp;
  296.     ino = (u_int16_t *)old_bufp->page;
  297.     np = (u_int16_t *)new_bufp->page;
  298.     op = (u_int16_t *)old_bufp->page;
  299.     last_bfp = NULL;
  300.     scopyto = (u_int16_t)copyto;    /* ANSI */
  301.  
  302.     n = ino[0] - 1;
  303.     while (n < ino[0]) {
  304.         if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {
  305.             if (__big_split(hashp, old_bufp,
  306.                 new_bufp, bufp, bufp->addr, obucket, &ret))
  307.                 return (-1);
  308.             old_bufp = ret.oldp;
  309.             if (!old_bufp)
  310.                 return (-1);
  311.             op = (u_int16_t *)old_bufp->page;
  312.             new_bufp = ret.newp;
  313.             if (!new_bufp)
  314.                 return (-1);
  315.             np = (u_int16_t *)new_bufp->page;
  316.             bufp = ret.nextp;
  317.             if (!bufp)
  318.                 return (0);
  319.             cino = (char *)bufp->page;
  320.             ino = (u_int16_t *)cino;
  321.             last_bfp = ret.nextp;
  322.         } else if (ino[n + 1] == OVFLPAGE) {
  323.             ov_addr = ino[n];
  324.             /*
  325.              * Fix up the old page -- the extra 2 are the fields
  326.              * which contained the overflow information.
  327.              */
  328.             ino[0] -= (moved + 2);
  329.             FREESPACE(ino) =
  330.                 scopyto - sizeof(u_int16_t) * (ino[0] + 3);
  331.             OFFSET(ino) = scopyto;
  332.  
  333.             bufp = __get_buf(hashp, ov_addr, bufp, 0);
  334.             if (!bufp)
  335.                 return (-1);
  336.  
  337.             ino = (u_int16_t *)bufp->page;
  338.             n = 1;
  339.             scopyto = hashp->BSIZE;
  340.             moved = 0;
  341.  
  342.             if (last_bfp)
  343.                 __free_ovflpage(hashp, last_bfp);
  344.             last_bfp = bufp;
  345.         }
  346.         /* Move regular sized pairs of there are any */
  347.         off = hashp->BSIZE;
  348.         for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
  349.             cino = (char *)ino;
  350.             key.data = (u_char *)cino + ino[n];
  351.             key.size = off - ino[n];
  352.             val.data = (u_char *)cino + ino[n + 1];
  353.             val.size = ino[n] - ino[n + 1];
  354.             off = ino[n + 1];
  355.  
  356.             if (__call_hash(hashp, key.data, key.size) == obucket) {
  357.                 /* Keep on old page */
  358.                 if (PAIRFITS(op, (&key), (&val)))
  359.                     putpair((char *)op, &key, &val);
  360.                 else {
  361.                     old_bufp =
  362.                         __add_ovflpage(hashp, old_bufp);
  363.                     if (!old_bufp)
  364.                         return (-1);
  365.                     op = (u_int16_t *)old_bufp->page;
  366.                     putpair((char *)op, &key, &val);
  367.                 }
  368.                 old_bufp->flags |= BUF_MOD;
  369.             } else {
  370.                 /* Move to new page */
  371.                 if (PAIRFITS(np, (&key), (&val)))
  372.                     putpair((char *)np, &key, &val);
  373.                 else {
  374.                     new_bufp =
  375.                         __add_ovflpage(hashp, new_bufp);
  376.                     if (!new_bufp)
  377.                         return (-1);
  378.                     np = (u_int16_t *)new_bufp->page;
  379.                     putpair((char *)np, &key, &val);
  380.                 }
  381.                 new_bufp->flags |= BUF_MOD;
  382.             }
  383.         }
  384.     }
  385.     if (last_bfp)
  386.         __free_ovflpage(hashp, last_bfp);
  387.     return (0);
  388. }
  389.  
  390. /*
  391.  * Add the given pair to the page
  392.  *
  393.  * Returns:
  394.  *    0 ==> OK
  395.  *    1 ==> failure
  396.  */
  397. extern int
  398. __addel(hashp, bufp, key, val)
  399.     HTAB *hashp;
  400.     BUFHEAD *bufp;
  401.     const DBT *key, *val;
  402. {
  403.     register u_int16_t *bp, *sop;
  404.     int do_expand;
  405.  
  406.     bp = (u_int16_t *)bufp->page;
  407.     do_expand = 0;
  408.     while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY))
  409.         /* Exception case */
  410.         if (bp[2] == FULL_KEY_DATA && bp[0] == 2)
  411.             /* This is the last page of a big key/data pair
  412.                and we need to add another page */
  413.             break;
  414.         else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {
  415.             bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  416.             if (!bufp)
  417.                 return (-1);
  418.             bp = (u_int16_t *)bufp->page;
  419.         } else
  420.             /* Try to squeeze key on this page */
  421.             if (FREESPACE(bp) > PAIRSIZE(key, val)) {
  422.                 squeeze_key(bp, key, val);
  423.                 return (0);
  424.             } else {
  425.                 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  426.                 if (!bufp)
  427.                     return (-1);
  428.                 bp = (u_int16_t *)bufp->page;
  429.             }
  430.  
  431.     if (PAIRFITS(bp, key, val))
  432.         putpair(bufp->page, key, val);
  433.     else {
  434.         do_expand = 1;
  435.         bufp = __add_ovflpage(hashp, bufp);
  436.         if (!bufp)
  437.             return (-1);
  438.         sop = (u_int16_t *)bufp->page;
  439.  
  440.         if (PAIRFITS(sop, key, val))
  441.             putpair((char *)sop, key, val);
  442.         else
  443.             if (__big_insert(hashp, bufp, key, val))
  444.                 return (-1);
  445.     }
  446.     bufp->flags |= BUF_MOD;
  447.     /*
  448.      * If the average number of keys per bucket exceeds the fill factor,
  449.      * expand the table.
  450.      */
  451.     hashp->NKEYS++;
  452.     if (do_expand ||
  453.         (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
  454.         return (__expand_table(hashp));
  455.     return (0);
  456. }
  457.  
  458. /*
  459.  *
  460.  * Returns:
  461.  *    pointer on success
  462.  *    NULL on error
  463.  */
  464. extern BUFHEAD *
  465. __add_ovflpage(hashp, bufp)
  466.     HTAB *hashp;
  467.     BUFHEAD *bufp;
  468. {
  469.     register u_int16_t *sp;
  470.     u_int16_t ndx, ovfl_num;
  471. #ifdef DEBUG1
  472.     int tmp1, tmp2;
  473. #endif
  474.     sp = (u_int16_t *)bufp->page;
  475.  
  476.     /* Check if we are dynamically determining the fill factor */
  477.     if (hashp->FFACTOR == DEF_FFACTOR) {
  478.         hashp->FFACTOR = sp[0] >> 1;
  479.         if (hashp->FFACTOR < MIN_FFACTOR)
  480.             hashp->FFACTOR = MIN_FFACTOR;
  481.     }
  482.     bufp->flags |= BUF_MOD;
  483.     ovfl_num = overflow_page(hashp);
  484. #ifdef DEBUG1
  485.     tmp1 = bufp->addr;
  486.     tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
  487. #endif
  488.     if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))
  489.         return (NULL);
  490.     bufp->ovfl->flags |= BUF_MOD;
  491. #ifdef DEBUG1
  492.     (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
  493.         tmp1, tmp2, bufp->ovfl->addr);
  494. #endif
  495.     ndx = sp[0];
  496.     /*
  497.      * Since a pair is allocated on a page only if there's room to add
  498.      * an overflow page, we know that the OVFL information will fit on
  499.      * the page.
  500.      */
  501.     sp[ndx + 4] = OFFSET(sp);
  502.     sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;
  503.     sp[ndx + 1] = ovfl_num;
  504.     sp[ndx + 2] = OVFLPAGE;
  505.     sp[0] = ndx + 2;
  506. #ifdef HASH_STATISTICS
  507.     hash_overflows++;
  508. #endif
  509.     return (bufp->ovfl);
  510. }
  511.  
  512. /*
  513.  * Returns:
  514.  *     0 indicates SUCCESS
  515.  *    -1 indicates FAILURE
  516.  */
  517. extern int
  518. __get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)
  519.     HTAB *hashp;
  520.     char *p;
  521.     u_int32_t bucket;
  522.     int is_bucket, is_disk, is_bitmap;
  523. {
  524.     register int fd, page, size;
  525.     int rsize;
  526.     u_int16_t *bp;
  527.  
  528.     fd = hashp->fp;
  529.     size = hashp->BSIZE;
  530.  
  531.     if ((fd == -1) || !is_disk) {
  532.         PAGE_INIT(p);
  533.         return (0);
  534.     }
  535.     if (is_bucket)
  536.         page = BUCKET_TO_PAGE(bucket);
  537.     else
  538.         page = OADDR_TO_PAGE(bucket);
  539.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  540.         ((rsize = read(fd, p, size)) == -1))
  541.         return (-1);
  542.     bp = (u_int16_t *)p;
  543.     if (!rsize)
  544.         bp[0] = 0;    /* We hit the EOF, so initialize a new page */
  545.     else
  546.         if (rsize != size) {
  547.             errno = EFTYPE;
  548.             return (-1);
  549.         }
  550.     if (!is_bitmap && !bp[0]) {
  551.         PAGE_INIT(p);
  552.     } else
  553.         if (hashp->LORDER != BYTE_ORDER) {
  554.             register int i, max;
  555.  
  556.             if (is_bitmap) {
  557.                 max = hashp->BSIZE >> 2; /* divide by 4 */
  558.                 for (i = 0; i < max; i++)
  559.                     M_32_SWAP(((int *)p)[i]);
  560.             } else {
  561.                 M_16_SWAP(bp[0]);
  562.                 max = bp[0] + 2;
  563.                 for (i = 1; i <= max; i++)
  564.                     M_16_SWAP(bp[i]);
  565.             }
  566.         }
  567.     return (0);
  568. }
  569.  
  570. /*
  571.  * Write page p to disk
  572.  *
  573.  * Returns:
  574.  *     0 ==> OK
  575.  *    -1 ==>failure
  576.  */
  577. extern int
  578. __put_page(hashp, p, bucket, is_bucket, is_bitmap)
  579.     HTAB *hashp;
  580.     char *p;
  581.     u_int32_t bucket;
  582.     int is_bucket, is_bitmap;
  583. {
  584.     register int fd, page, size;
  585.     int wsize;
  586.  
  587.     size = hashp->BSIZE;
  588.     if ((hashp->fp == -1) && open_temp(hashp))
  589.         return (-1);
  590.     fd = hashp->fp;
  591.  
  592.     if (hashp->LORDER != BYTE_ORDER) {
  593.         register int i;
  594.         register int max;
  595.  
  596.         if (is_bitmap) {
  597.             max = hashp->BSIZE >> 2;    /* divide by 4 */
  598.             for (i = 0; i < max; i++)
  599.                 M_32_SWAP(((int *)p)[i]);
  600.         } else {
  601.             max = ((u_int16_t *)p)[0] + 2;
  602.             for (i = 0; i <= max; i++)
  603.                 M_16_SWAP(((u_int16_t *)p)[i]);
  604.         }
  605.     }
  606.     if (is_bucket)
  607.         page = BUCKET_TO_PAGE(bucket);
  608.     else
  609.         page = OADDR_TO_PAGE(bucket);
  610.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  611.         ((wsize = write(fd, p, size)) == -1))
  612.         /* Errno is set */
  613.         return (-1);
  614.     if (wsize != size) {
  615.         errno = EFTYPE;
  616.         return (-1);
  617.     }
  618.     return (0);
  619. }
  620.  
  621. #define BYTE_MASK    ((1 << INT_BYTE_SHIFT) -1)
  622. /*
  623.  * Initialize a new bitmap page.  Bitmap pages are left in memory
  624.  * once they are read in.
  625.  */
  626. extern int
  627. __ibitmap(hashp, pnum, nbits, ndx)
  628.     HTAB *hashp;
  629.     int pnum, nbits, ndx;
  630. {
  631.     u_int32_t *ip;
  632.     int clearbytes, clearints;
  633.  
  634.     if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL)
  635.         return (1);
  636.     hashp->nmaps++;
  637.     clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
  638.     clearbytes = clearints << INT_TO_BYTE;
  639.     (void)memset((char *)ip, 0, clearbytes);
  640.     (void)memset(((char *)ip) + clearbytes, 0xFF,
  641.         hashp->BSIZE - clearbytes);
  642.     ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
  643.     SETBIT(ip, 0);
  644.     hashp->BITMAPS[ndx] = (u_int16_t)pnum;
  645.     hashp->mapp[ndx] = ip;
  646.     return (0);
  647. }
  648.  
  649. static u_int32_t
  650. first_free(map)
  651.     u_int32_t map;
  652. {
  653.     register u_int32_t i, mask;
  654.  
  655.     mask = 0x1;
  656.     for (i = 0; i < BITS_PER_MAP; i++) {
  657.         if (!(mask & map))
  658.             return (i);
  659.         mask = mask << 1;
  660.     }
  661.     return (i);
  662. }
  663.  
  664. static u_int16_t
  665. overflow_page(hashp)
  666.     HTAB *hashp;
  667. {
  668.     register u_int32_t *freep;
  669.     register int max_free, offset, splitnum;
  670.     u_int16_t addr;
  671.     int bit, first_page, free_bit, free_page, i, in_use_bits, j;
  672. #ifdef DEBUG2
  673.     int tmp1, tmp2;
  674. #endif
  675.     splitnum = hashp->OVFL_POINT;
  676.     max_free = hashp->SPARES[splitnum];
  677.  
  678.     free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
  679.     free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  680.  
  681.     /* Look through all the free maps to find the first free block */
  682.     first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
  683.     for ( i = first_page; i <= free_page; i++ ) {
  684.         if (!(freep = (u_int32_t *)hashp->mapp[i]) &&
  685.             !(freep = fetch_bitmap(hashp, i)))
  686.             return (0);
  687.         if (i == free_page)
  688.             in_use_bits = free_bit;
  689.         else
  690.             in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
  691.         
  692.         if (i == first_page) {
  693.             bit = hashp->LAST_FREED &
  694.                 ((hashp->BSIZE << BYTE_SHIFT) - 1);
  695.             j = bit / BITS_PER_MAP;
  696.             bit = bit & ~(BITS_PER_MAP - 1);
  697.         } else {
  698.             bit = 0;
  699.             j = 0;
  700.         }
  701.         for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
  702.             if (freep[j] != ALL_SET)
  703.                 goto found;
  704.     }
  705.  
  706.     /* No Free Page Found */
  707.     hashp->LAST_FREED = hashp->SPARES[splitnum];
  708.     hashp->SPARES[splitnum]++;
  709.     offset = hashp->SPARES[splitnum] -
  710.         (splitnum ? hashp->SPARES[splitnum - 1] : 0);
  711.  
  712. #define    OVMSG    "HASH: Out of overflow pages.  Increase page size\n"
  713.     if (offset > SPLITMASK) {
  714.         if (++splitnum >= NCACHED) {
  715.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  716.             return (0);
  717.         }
  718.         hashp->OVFL_POINT = splitnum;
  719.         hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  720.         hashp->SPARES[splitnum-1]--;
  721.         offset = 1;
  722.     }
  723.  
  724.     /* Check if we need to allocate a new bitmap page */
  725.     if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
  726.         free_page++;
  727.         if (free_page >= NCACHED) {
  728.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  729.             return (0);
  730.         }
  731.         /*
  732.          * This is tricky.  The 1 indicates that you want the new page
  733.          * allocated with 1 clear bit.  Actually, you are going to
  734.          * allocate 2 pages from this map.  The first is going to be
  735.          * the map page, the second is the overflow page we were
  736.          * looking for.  The init_bitmap routine automatically, sets
  737.          * the first bit of itself to indicate that the bitmap itself
  738.          * is in use.  We would explicitly set the second bit, but
  739.          * don't have to if we tell init_bitmap not to leave it clear
  740.          * in the first place.
  741.          */
  742.         if (__ibitmap(hashp,
  743.             (int)OADDR_OF(splitnum, offset), 1, free_page))
  744.             return (0);
  745.         hashp->SPARES[splitnum]++;
  746. #ifdef DEBUG2
  747.         free_bit = 2;
  748. #endif
  749.         offset++;
  750.         if (offset > SPLITMASK) {
  751.             if (++splitnum >= NCACHED) {
  752.                 (void)write(STDERR_FILENO, OVMSG,
  753.                     sizeof(OVMSG) - 1);
  754.                 return (0);
  755.             }
  756.             hashp->OVFL_POINT = splitnum;
  757.             hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  758.             hashp->SPARES[splitnum-1]--;
  759.             offset = 0;
  760.         }
  761.     } else {
  762.         /*
  763.          * Free_bit addresses the last used bit.  Bump it to address
  764.          * the first available bit.
  765.          */
  766.         free_bit++;
  767.         SETBIT(freep, free_bit);
  768.     }
  769.  
  770.     /* Calculate address of the new overflow page */
  771.     addr = OADDR_OF(splitnum, offset);
  772. #ifdef DEBUG2
  773.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  774.         addr, free_bit, free_page);
  775. #endif
  776.     return (addr);
  777.  
  778. found:
  779.     bit = bit + first_free(freep[j]);
  780.     SETBIT(freep, bit);
  781. #ifdef DEBUG2
  782.     tmp1 = bit;
  783.     tmp2 = i;
  784. #endif
  785.     /*
  786.      * Bits are addressed starting with 0, but overflow pages are addressed
  787.      * beginning at 1. Bit is a bit addressnumber, so we need to increment
  788.      * it to convert it to a page number.
  789.      */
  790.     bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
  791.     if (bit >= hashp->LAST_FREED)
  792.         hashp->LAST_FREED = bit - 1;
  793.  
  794.     /* Calculate the split number for this page */
  795.     for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
  796.     offset = (i ? bit - hashp->SPARES[i - 1] : bit);
  797.     if (offset >= SPLITMASK)
  798.         return (0);    /* Out of overflow pages */
  799.     addr = OADDR_OF(i, offset);
  800. #ifdef DEBUG2
  801.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  802.         addr, tmp1, tmp2);
  803. #endif
  804.  
  805.     /* Allocate and return the overflow page */
  806.     return (addr);
  807. }
  808.  
  809. /*
  810.  * Mark this overflow page as free.
  811.  */
  812. extern void
  813. __free_ovflpage(hashp, obufp)
  814.     HTAB *hashp;
  815.     BUFHEAD *obufp;
  816. {
  817.     register u_int16_t addr;
  818.     u_int32_t *freep;
  819.     int bit_address, free_page, free_bit;
  820.     u_int16_t ndx;
  821.  
  822.     addr = obufp->addr;
  823. #ifdef DEBUG1
  824.     (void)fprintf(stderr, "Freeing %d\n", addr);
  825. #endif
  826.     ndx = (((u_int16_t)addr) >> SPLITSHIFT);
  827.     bit_address =
  828.         (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
  829.      if (bit_address < hashp->LAST_FREED)
  830.         hashp->LAST_FREED = bit_address;
  831.     free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
  832.     free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  833.  
  834.     if (!(freep = hashp->mapp[free_page]))
  835.         freep = fetch_bitmap(hashp, free_page);
  836. #ifdef DEBUG
  837.     /*
  838.      * This had better never happen.  It means we tried to read a bitmap
  839.      * that has already had overflow pages allocated off it, and we
  840.      * failed to read it from the file.
  841.      */
  842.     if (!freep)
  843.         assert(0);
  844. #endif
  845.     CLRBIT(freep, free_bit);
  846. #ifdef DEBUG2
  847.     (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
  848.         obufp->addr, free_bit, free_page);
  849. #endif
  850.     __reclaim_buf(hashp, obufp);
  851. }
  852.  
  853. /*
  854.  * Returns:
  855.  *     0 success
  856.  *    -1 failure
  857.  */
  858. static int
  859. open_temp(hashp)
  860.     HTAB *hashp;
  861. {
  862.     sigset_t set, oset;
  863.     static char namestr[] = "_hashXXXXXX";
  864.  
  865.     /* Block signals; make sure file goes away at process exit. */
  866.     (void)sigfillset(&set);
  867.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  868.     if ((hashp->fp = mkstemp(namestr)) != -1) {
  869.         (void)unlink(namestr);
  870. #ifndef macintosh
  871.         (void)fcntl(hashp->fp, F_SETFD, 1);
  872. #endif
  873.     }
  874.     (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
  875.     return (hashp->fp != -1 ? 0 : -1);
  876. }
  877.  
  878. /*
  879.  * We have to know that the key will fit, but the last entry on the page is
  880.  * an overflow pair, so we need to shift things.
  881.  */
  882. static void
  883. squeeze_key(sp, key, val)
  884.     u_int16_t *sp;
  885.     const DBT *key, *val;
  886. {
  887.     register char *p;
  888.     u_int16_t free_space, n, off, pageno;
  889.  
  890.     p = (char *)sp;
  891.     n = sp[0];
  892.     free_space = FREESPACE(sp);
  893.     off = OFFSET(sp);
  894.  
  895.     pageno = sp[n - 1];
  896.     off -= key->size;
  897.     sp[n - 1] = off;
  898.     memmove(p + off, key->data, key->size);
  899.     off -= val->size;
  900.     sp[n] = off;
  901.     memmove(p + off, val->data, val->size);
  902.     sp[0] = n + 2;
  903.     sp[n + 1] = pageno;
  904.     sp[n + 2] = OVFLPAGE;
  905.     FREESPACE(sp) = free_space - PAIRSIZE(key, val);
  906.     OFFSET(sp) = off;
  907. }
  908.  
  909. static u_int32_t *
  910. fetch_bitmap(hashp, ndx)
  911.     HTAB *hashp;
  912.     int ndx;
  913. {
  914.     if (ndx >= hashp->nmaps)
  915.         return (NULL);
  916.     if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL)
  917.         return (NULL);
  918.     if (__get_page(hashp,
  919.         (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
  920.         free(hashp->mapp[ndx]);
  921.         return (NULL);
  922.     }
  923.     return (hashp->mapp[ndx]);
  924. }
  925.  
  926. #ifdef DEBUG4
  927. int
  928. print_chain(addr)
  929.     int addr;
  930. {
  931.     BUFHEAD *bufp;
  932.     short *bp, oaddr;
  933.  
  934.     (void)fprintf(stderr, "%d ", addr);
  935.     bufp = __get_buf(hashp, addr, NULL, 0);
  936.     bp = (short *)bufp->page;
  937.     while (bp[0] && ((bp[bp[0]] == OVFLPAGE) ||
  938.         ((bp[0] > 2) && bp[2] < REAL_KEY))) {
  939.         oaddr = bp[bp[0] - 1];
  940.         (void)fprintf(stderr, "%d ", (int)oaddr);
  941.         bufp = __get_buf(hashp, (int)oaddr, bufp, 0);
  942.         bp = (short *)bufp->page;
  943.     }
  944.     (void)fprintf(stderr, "\n");
  945. }
  946. #endif
  947.